package com.congee02.template.heap;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class Heap {

    private int[] elems;
    private int size;

    public Heap(int capacity) {
        this.elems = new int[capacity];
        this.size = 0;
    }

    private void siftUp(int i) {
        int cur = i;
        while (cur > 0 && elems[cur] < elems[parent(cur)]) {
            swap(cur, parent(cur));
            cur = parent(cur);
        }
    }

    private void siftDown(int i) {
        int cur = i;
        int left = leftChild(i);
        while (left < size) {

            int right = rightChild(cur);

            int minChild = right < size && elems[right] < elems[left] ? right : left;

            int allMin = Math.min( elems[cur], elems[minChild] );

            if (allMin == elems[cur]) {
                return;
            }

            swap( minChild, cur );

            cur = minChild;
            left = leftChild(cur);

        }
    }

    private int leftChild(int i) {
        return 2 * i + 1;
    }

    private int rightChild(int i) {
        return leftChild(i) + 1;
    }

    private void swap(int x, int y) {
        int t = elems[x];
        elems[x] = elems[y];
        elems[y] = t;
    }

    private int parent(int i) {
        return (i - 1) / 2;
    }

    public void offer(int value) {
        elems[size] = value;
        siftUp(size ++);
    }

    public int poll() {
        int ans = elems[0];
        elems[0] = elems[size - 1];
        siftDown(0);
        size --;
        return ans;
    }

    public static int[] generateRandomArray(int minSize, int maxSize, int minValue, int maxValue) {
        Random random = new Random();
        // 生成范围在 [minSize, maxSize] 之间的随机数组大小
        int size = random.nextInt(maxSize - minSize + 1) + minSize;
        int[] array = new int[size];

        for (int i = 0; i < size; i++) {
            // 生成范围在 [minValue, maxValue] 之间的随机整数
            array[i] = random.nextInt(maxValue - minValue + 1) + minValue;
        }

        return array;
    }

    public static boolean isSorted(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1]) {
                return false;  // 如果当前元素大于下一个元素，说明未排序
            }
        }
        return true;  // 如果没有违反顺序的元素，说明数组已排序
    }

    public static void main(String[] args) {

        final int N = 10000;

        Heap s = new Heap(10000);

        for (int i = 0 ; i < N ; i ++ ) {

            int[] nums = generateRandomArray(0, 10000, -1000, 1000);
            for (int x : nums) {
                s.offer(x);
            }
            for (int j = 0 ; j < nums.length ; j ++ ) {
                nums[j] = s.poll();
            }
            if (! isSorted(nums)) {
                throw new IllegalStateException("OP");
            }

        }

    }

}
